package SwordFingerOffer;

public class Q04_FindNumIn2DArray {



    //遍历O(N)

//            [1,   4,  7, 11, 15]
//            [2,   5,  8, 12, 19]
//            [3,   6,  9, 16, 22]
//            [10, 13, 14, 17, 24]
//            [18, 21, 23, 26, 30]
    //二分O(logN)
    public boolean findNumberIn2DArray(int[][] matrix, int target) {


        return process(matrix,target, matrix.length - 1, 0);

    }


    //以一边运行一边淘汰(某一行/某一列)的观点看
    //全流程不会错过匹配值
    //不要想二分了 不好想 不好记
    public static boolean process(int[][] matrix, int target, int row, int col){
         // 跑完了都找不到
        if (row < 0 || col == matrix[0].length){
            return false;
        }

        //匹配到
        if (matrix[row][col] == target){
            return true;
        }
        //没匹配到
        if (matrix[row][col] > target){
            return process(matrix, target, row - 1, col);
        }else {
            return process(matrix, target, row, col + 1);
        }
    }

}
